{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def reorganizeString(self, S: str) -> str:\n",
    "        d = {}\n",
    "        for c in set(S):\n",
    "            d[c] = S.count(c)\n",
    "        sort_orders = sorted(d.items(), key=lambda x: x[1], reverse=True)\n",
    "        left = sort_orders[0][1]\n",
    "        for key,value in sort_orders[1:]:\n",
    "            left -= value\n",
    "        if left % 2 != 0:\n",
    "            last_s = None\n",
    "            s = \"\"\n",
    "            orders = [list(t) for t in sort_orders]\n",
    "            print(orders)\n",
    "            while 1:\n",
    "                if last_s == s:\n",
    "                    break\n",
    "                last_s = s\n",
    "                for i in range(len(orders)):\n",
    "                    if orders[i][1] > 0:\n",
    "                        s += orders[i][0]\n",
    "                        orders[i][1] -= 1\n",
    "            return s\n",
    "        else:\n",
    "            return \"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Wrong Answer\n",
    "\n",
    "Input\n",
    "\"vvvlo\"\n",
    "\n",
    "stdout\n",
    "[['v', 3], ['o', 1], ['l', 1]]\n",
    "\n",
    "Output\n",
    "\"volvv\"\n",
    "\n",
    "Expected\n",
    "\"vlvov\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def reorganizeString(self, S: str) -> str:\n",
    "        d = {}\n",
    "        for c in set(S):\n",
    "            d[c] = S.count(c)\n",
    "        if len(d.keys()) == 1:\n",
    "            return \"\"\n",
    "        sort_orders = sorted(d.items(), key=lambda x: x[1], reverse=True)\n",
    "        left = sort_orders[0][1]\n",
    "        for key,value in sort_orders[1:]:\n",
    "            left -= value\n",
    "        if left % 2 != 0:\n",
    "            orders = [list(t) for t in sort_orders]\n",
    "            print(orders)\n",
    "            \n",
    "            s = \"\"\n",
    "            while 1:\n",
    "                if len(orders) == 0:\n",
    "                    break\n",
    "                if len(orders) == 1:\n",
    "                    if orders[0][1] > 1:\n",
    "                        return \"\"\n",
    "                    else:\n",
    "                        s += orders[0][0]\n",
    "                        break\n",
    "                orders = sorted(orders, key=lambda x: x[1], reverse=True)\n",
    "                a, b = orders[:2]\n",
    "                print(a, b)\n",
    "                while 1:\n",
    "                    if a[1] == 0 and b[1] == 0:\n",
    "                        break\n",
    "                    if b[1] > 0:\n",
    "                        s += a[0]\n",
    "                        s += b[0]\n",
    "                        a[1] -= 1\n",
    "                        b[1] -= 1\n",
    "                    else:\n",
    "                        # b[1] <= 0\n",
    "                        orders = [[a[0], a[1]]] + orders[2:]\n",
    "                        break\n",
    "            return s\n",
    "        else:\n",
    "            return \"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Wrong Answer\n",
    "\n",
    "Input\n",
    "\"abbabbaaab\"\n",
    "\n",
    "Output\n",
    "\"\"\n",
    "\n",
    "Expected\n",
    "\"ababababab\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://leetcode.com/problems/reorganize-string\n",
    "\n",
    "\n",
    "\n",
    "Runtime: 24 ms, faster than 96.88% of Python3 online submissions for Reorganize String.\n",
    "Memory Usage: 14.3 MB, less than 11.34% of Python3 online submissions for Reorganize String.\n",
    "\n",
    "\n",
    "\n",
    "```python\n",
    "class Solution:\n",
    "    def reorganizeString(self, S: str) -> str:\n",
    "        d = {}\n",
    "        for c in set(S):\n",
    "            d[c] = S.count(c)\n",
    "        if len(d.keys()) == 1:\n",
    "            return \"\"\n",
    "        sort_orders = sorted(d.items(), key=lambda x: x[1], reverse=True)\n",
    "        orders = [list(t) for t in sort_orders]\n",
    "        print(orders)\n",
    "\n",
    "        s = \"\"\n",
    "        while 1:\n",
    "            if len(orders) == 0:\n",
    "                break\n",
    "            if len(orders) == 1:\n",
    "                if orders[0][1] > 1:\n",
    "                    return \"\"\n",
    "                else:\n",
    "                    s += orders[0][0]\n",
    "                    break\n",
    "            orders = sorted(orders, key=lambda x: x[1], reverse=True)\n",
    "            a, b = orders[:2]\n",
    "            if a[1] == 0 and b[1] == 0:\n",
    "                return s\n",
    "            while 1:\n",
    "                if a[1] == 0 and b[1] == 0:\n",
    "                    break\n",
    "                if b[1] > 0:\n",
    "                    s += a[0]\n",
    "                    s += b[0]\n",
    "                    a[1] -= 1\n",
    "                    b[1] -= 1\n",
    "                else:\n",
    "                    # b[1] <= 0\n",
    "                    orders = [[a[0], a[1]]] + orders[2:]\n",
    "                    break\n",
    "        return s\n",
    "```\n",
    "\n",
    "spent 2 hours\n",
    "\n",
    "tried 4 times"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}